package ljl.alg.wangzheng_camp.round1.backtrack;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class _93_recover_ip {
    
    int[] segs = new int[4];
    List<String> res = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        dfs(s, 0, 0);
        return res;
    }
    void dfs(String s, int seg, int start) {
        if (seg == 4) {
            if (start == s.length()) {
                res.add(IntStream.of(segs).mapToObj(String::valueOf).collect(Collectors.joining(".")));
            }
            return;
        }
        if (start == s.length())
            return;
        if (s.charAt(start) == '0') {
            segs[seg] = 0;
            dfs(s, seg + 1, start + 1);
            return;
        }
        int num = 0;
        for (int i = start; i < s.length(); i++) {
            num = num * 10 + s.charAt(i) - '0';
            if (num >= 0 && num <= 255) {
                segs[seg] = num;
                dfs(s, seg + 1, i + 1);
            } else
                return;
        }
    }
}
